"""
912. 排序数组
中等
相关标签
premium lock icon
相关企业
给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。



示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。
示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：请注意，nums 的值不一定唯一。


提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

"""
import random
from typing import List


class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        """
        快排
        :param nums:
        :return:
        """
        def sort(nums:List[int]):
            if len(nums)<=1:
                return nums
            ch = random.choice(nums)
            small = []
            equals = []
            large = []
            for num in nums:
                if ch>num:
                    small.append(num)
                elif ch<num:
                    large.append(num)
                else:
                    equals.append(num)
            return sort(small) + equals + sort(large)
        return sort(nums)

if __name__ == '__main__':
    s = Solution()
    list1 = [5, 2, 3, 1]
    print(s.sortArray(list1))
    list2 = [5, 1, 1, 2, 0, 0]
    print(s.sortArray(list2))
